Hashing Review Part 2  

  The following review questions were covered in Labs 02 and 03 and are questions taken from the course website. NOT ALL questions from the course website were discussed in lab.
Please note that the information presented here does not necessarily represent a complete answer to the review question. The information is intended to spark student's memory for those who attended lab OR provide a base (hint) from where to start for those students who did not attend lab.

  Question 1: Insert the given keys into the table provided using Brent's method.

RECORD KEYS: 14,51,37,18,16,25,36,17,11,27
HASH FUNCTION: hash(key) = key mod 11
INCREMENT FUNCTION: increment(key) = Quotient(Key/11) mod 11
  
 

 
 

 


  Question 2: Why is deletion of keys/records from a hash table loaded using open addressing so problematic?
  
   
You either have to reconstruct the table or use tombstones.
  

  Question 3: How does 2-pass loading affect the distribution of records in a hashed file?
  
   
Will end up with more, shorter chains if there is no moving of records OR less moving of records.
  

  Question 4: How does chaining rather than progressive overflow affect performance in file retrieval of records in a hashed file?
  
   
Can expect shorter chains, and therefore a smaller average probe count.
  

  Question 5: What is a trie?
  
   
See extendible hashing structure.
  

  Question 6: What is a perfect hashing function?
  
   
One where each key is loaded to a unique home address.
  

  Question 7: What is the major requirement in a file's behaviour that would make the use of hashing a reasonable option?
  
   
A file that is not highly dynamic (ie. - one where there is not alot of change).
  

  Question 8: The Binary Tree Insertion Method of Collision Resolution in hash tables is quite complicated and may result in the movement of a LOT of keys by the time the entire table is loaded. Why bother? In other workds, why implement such a complicated and time-consuming algorithm to load a hash table?
  
   
Because the end result represents the best possible placement of keys (might be better than a 2 pass load). You are minimizing the overall chain length as opposed to reducing individual chains.
  


BACK

© Copyright 2002
Questions? Please Email: gwen@cpsc.ucalgary.ca
Last modified December 4, 2002